package com.jdaw.datastructure.huffmancode;

import java.io.*;
import java.util.*;

public class HuffmanCode {
    public static void main(String[] args) {
//        String content="i like like like java do you like a java";
//        byte[] contentBytes = content.getBytes();
//        byte[] res=huffmanZip(contentBytes);
//        byte[] src=decode(huffmanCodes,res);
//        System.out.println(new String(src));
        String src="D://CodeFiles//10.png";
        String dst="D://CodeFiles//9.zip";
        unZipFile(dst,src);
    }

    //文件压缩
    public static void zipFile(String srcFile,String dstFile) {
        //srcFile是源文件路径，dstFile是目标文件路径
        //创建输出流
        OutputStream os=null;
        ObjectOutputStream oos=null;
        //创建文件输入流
        FileInputStream is=null;
        try {
             is= new FileInputStream(srcFile);
            //创建一个和源文件一样的byte[]
            byte[] b=new byte[is.available()];
            //读取文件
            is.read(b);
            byte[] huffmanBytes=huffmanZip(b);

            os=new FileOutputStream(dstFile);
            oos=new ObjectOutputStream(os);
            oos.writeObject(huffmanBytes);//直接把byte对象输出出去，利于以后解码
            //把赫夫曼编码也写入压缩文件
            oos.writeObject(huffmanCodes);
        } catch (Exception e) {
            e.printStackTrace();
        }finally {
            try {
                is.close();
                os.close();
                oos.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

    }

    //文件的解压
    public static void unZipFile(String zipFile,String dstFile) {
        //定义文件输入流
        InputStream is=null;
        //对象输入流
        ObjectInputStream ois=null;
        OutputStream os=null;
        try {
            is=new FileInputStream(zipFile);
            ois=new ObjectInputStream(is);
            byte[] huffmanBytes=(byte[])ois.readObject();
            //读取赫夫曼编码表
            Map<Byte,String> huffmanCodes=(Map<Byte, String>) ois.readObject();
            byte[] bytes=decode(huffmanCodes,huffmanBytes);
            os=new FileOutputStream(dstFile);
            os.write(bytes);
        } catch (Exception e) {
            e.printStackTrace();
        }finally{
            try {
                is.close();
                os.close();
                ois.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

    //数据的解码
    //1.把一个byte转为string
    private static String byteToBitString(boolean flag,byte b){
        //flag标识一下是否需要补高位
        int t=b;
        if(flag){
            t |=256;
        }
        String str=Integer.toBinaryString(t);
        //若t为正数，-8以后就越界了
        if(flag){
            return str.substring(str.length()-8);
        }else{
            return str;
        }
    }
    //2.最终的解码
    private static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanBytes){
        //huffmanBytes是huffman编码最终得到的[-88,...]
        StringBuilder stringBuilder1 = new StringBuilder();
        for(int i=0;i<huffmanBytes.length;i++){
            boolean flag=(i==huffmanBytes.length-1);
            stringBuilder1.append(byteToBitString(!flag,huffmanBytes[i]));
        }
        //将map的key和value反转
        Map<String,Byte> map=new HashMap<String,Byte>();
        for(Map.Entry<Byte,String> entry:huffmanCodes.entrySet()){
            map.put(entry.getValue(),entry.getKey());
        }

        //遍历stringbuilder放入集合中
        List<Byte> list=new ArrayList<>();
        for(int i=0;i<stringBuilder1.length();){
            int count=1;//轮番取，让取的字符串不断变长
            boolean flag=false;
            Byte b=null;
            while(!flag){
                String str=stringBuilder1.substring(i,i+count);
                b=map.get(str);
                if(b!=null){
                    flag=true;
                }else{
                    count++;
                }
            }
            list.add(b);
            i+=count;
        }
        byte[] b=new byte[list.size()];
        for(int j=0;j<list.size();j++){
            b[j]=list.get(j);
        }
        return b;
    }


    //方法整理
    public static byte[] huffmanZip(byte[] bytes){
        List<Node> nodes=getNodes(bytes);
        Node huffmanTreeRoot=createHuffmanTree(nodes);
        Map<Byte,String> huffmanCodes=getCodes(huffmanTreeRoot);
        byte[] res=zip(bytes,huffmanCodes);
        return res;
    }

    //生成赫夫曼编码的最终结果，生成一个byte[]
    private static byte[] zip(byte[] bytes,Map<Byte,String> huffmanCodes){
        StringBuilder stringBuilder=new StringBuilder();
        for(byte b:bytes){
            stringBuilder.append(huffmanCodes.get(b));
        }
        //将“1001...”转为byte[]发送
        int len;
        if(stringBuilder.length()%8==0){
            len=stringBuilder.length()/8;
        }else{
            len=stringBuilder.length()/8+1;
        }
        byte[] by=new byte[len];
        int index=0;
        for(int i=0;i<stringBuilder.length();i+=8){
            String str;
            //可能最后没有8位取
            if(i+8>stringBuilder.length()){
                str=stringBuilder.substring(i);
            }else{
                str=stringBuilder.substring(i,i+8);
            }
            //转为byte[],如“10101000”->-88
            by[index]=(byte)Integer.parseInt(str,2);
            index++;
        }
        return by;
    }


    //重载getCodes,使传入了一个节点就能返回一个map
    private static Map<Byte,String> getCodes(Node root){
        if(root==null){
            return null;
        }else{
            getCodes(root.left,"0",stringBuilder);
            getCodes(root.right,"1",stringBuilder);
        }
        return huffmanCodes;
    }

    //生成赫夫曼编码表
    //放在map中
    static Map<Byte,String> huffmanCodes=new HashMap<Byte,String>();
    static StringBuilder stringBuilder=new StringBuilder();//拼接路径
    private static void getCodes(Node node,String code,StringBuilder stringBuilder){
        //code是路径，左子节点为0，右子节点为1
        StringBuilder stringBuilder2=new StringBuilder(stringBuilder);
        stringBuilder2.append(code);
        if(node.data==null){//为空说明为非叶子节点
            //向左向右递归
            getCodes(node.left,"0",stringBuilder2);
            getCodes(node.right,"1",stringBuilder2);
        }else{
            huffmanCodes.put(node.data,stringBuilder2.toString());
        }
    }

    //前序遍历方法
    public static void preOrder(Node root){
        if(root!=null){
            root.preOrder();
        }else{
            System.out.println("该树为空");
        }
    }


    public static List<Node> getNodes(byte[] bytes){
        //可以用map统计每一个byte出现的次数
        ArrayList<Node> nodes = new ArrayList<>();
        HashMap<Byte,Integer> counts = new HashMap<>();
        for(byte b:bytes){
            Integer count=counts.get(b);
            if(count==null){
                counts.put(b,1);
            }else{
                counts.put(b,count+1);
            }
        }
        //把每个键值对转换为一个node对象
        //遍历map
        for(Map.Entry<Byte,Integer> entry:counts.entrySet()){
            nodes.add(new Node(entry.getKey(),entry.getValue()));
        }
        return nodes;
    }

    public static Node createHuffmanTree(List<Node> nodes){
        while(nodes.size()>1){
            Collections.sort(nodes);
            //取出权值第一第二小的节点
            Node leftNode=nodes.get(0);
            Node rightNode=nodes.get(1);
            Node parent=new Node(null,leftNode.weight+rightNode.weight);
            parent.left=leftNode;
            parent.right=rightNode;
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(parent);
        }
        return nodes.get(0);
    }
}

class Node implements Comparable<Node>{
    Byte data;//存放字母的asicii码
    int weight;//存放权值
    Node left;
    Node right;

    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node o) {
        return this.weight-o.weight;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }
    //写一个前序遍历
    public void preOrder(){
        System.out.println(this);
        if(this.left!=null){
            this.left.preOrder();
        }
        if(this.right!=null){
            this.right.preOrder();
        }
    }
}
